Modular Exponentiation

Modular exponentiation is an efficient method for computing large powers modulo some integer, commonly used in cryptography and other fields involving large number computations. This technique significantly reduces the time complexity from (O(b)) to (O(\log b)), making it feasible to compute large powers quickly.

Basics of Modular Exponentiation

The goal is to compute (a^b \mod m) efficiently. Instead of multiplying (a) by itself (b) times, we use an algorithm that divides the exponentiation process in half each time, working in logarithmic time.

Example

To compute (3^13 \mod 7):

1. Break down the exponent 13 into powers of 2 (binary representation).
2. Compute each power modulo 7 and combine using properties of modular arithmetic.

Algorithm: Fast Exponentiation

Recursive Method

A recursive approach to modular exponentiation calculates each intermediate step modulo (m).

Python Implementation

def mod_exp(base, exponent, modulus):
    if exponent == 0:
        return 1
    half_exp = mod_exp(base, exponent // 2, modulus)
    half_exp = (half_exp * half_exp) % modulus
    if exponent % 2 != 0:
        half_exp = (half_exp * base) % modulus
    return half_exp

C++ Implementation

#include <iostream>
using namespace std;

long long mod_exp(long long base, long long exponent, long long modulus) {
    if (exponent == 0) {
        return 1;
    }
    
    long long half_exp = mod_exp(base, exponent / 2, modulus);
    half_exp = (half_exp * half_exp) % modulus;
    
    if (exponent % 2 != 0) {
        half_exp = (half_exp * base) % modulus;
    }
    
    return half_exp;
}

int main() {
    long long base, exponent, modulus;
    cout << "Enter base, exponent, and modulus: ";
    cin >> base >> exponent >> modulus;
    
    cout << "Result: " << mod_exp(base, exponent, modulus) << endl;
    
    return 0;
}

Iterative Method

An iterative version avoids recursion by using bitwise operations to halve the exponent at each step.

Python Implementation

def mod_exp(base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if (exponent % 2) == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

C++ Implementation

#include <iostream>
using namespace std;

long long mod_exp(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base = base % modulus;  // Ensure base is within the modulus
    
    while (exponent > 0) {
        // If exponent is odd, multiply result by the base
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        // Halve the exponent and square the base
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    
    return result;
}

int main() {
    long long base, exponent, modulus;
    cout << "Enter base, exponent, and modulus: ";
    cin >> base >> exponent >> modulus;
    
    cout << "Result: " << mod_exp(base, exponent, modulus) << endl;
    
    return 0;
}

Applications of Modular Exponentiation

Modular exponentiation has applications in areas where fast computation of powers modulo a number is essential:

1. Cryptography: Used in RSA and Diffie-Hellman protocols to secure data by performing computations on large numbers efficiently.
2. Digital Signatures: Ensures message integrity and authenticity by leveraging fast modular power computations.
3. Random Number Generation: Modular exponentiation helps generate random sequences within a specific range.

Time Complexity

The time complexity of modular exponentiation, both in the recursive and iterative versions, is O(logb), where b is the exponent.